package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/10 10:30
 * https://leetcode.cn/problems/minimum-genetic-mutation/
 */
public class Title433II {

    public static int minMutation(String start, String end, String[] bank) {
        Set<String> banks = new HashSet<>();
        for (int i = 0; i < bank.length; i++) {
            banks.add(bank[i]);
        }
        if (!banks.contains(end)) {
            return -1;
        }
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(start);
        Map<String, Integer> visited = new HashMap<>();
        visited.put(start, 0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String poll = queue.poll();
                char[] c = {'A', 'C', 'G', 'T'};
                Integer len = visited.get(poll);
                for (int j = 0; j < poll.length(); j++) {
                    char[] s = poll.toCharArray();
                    for (int k = 0; k < c.length; k++) {
                        if (s[j] != c[k]) {
                            s[j] = c[k];
                            String newS = String.valueOf(s);
                            if (newS.equals(end)) {
                                return len + 1;
                            }
                            if (banks.contains(newS) && !visited.containsKey(newS)) {
                                queue.offer(newS);
                                visited.put(newS, len + 1);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String start = "AACCGGTT";
        String end = "AACCGGTA";
        String [] bank = {"AACCGGTA"};
        minMutation(start, end, bank);
    }
}
